// 并查集
// https://www.bilibili.com/video/BV1jv411a7LK/?spm_id_from=333.337.search-card.all.click&vd_source=4fd973d19cb5506a7c9f2d59e8ab5165
// 并查集需要实现三个方法，init, find, union

const HashMap = require('./hashmap.js');

class DisJoint {
    /**
     * 并查集的init，
     * 将每一个元素的祖先节点指向自身
     * @param {number} n n个元素
     */
    constructor(n) {
        this.n = n; // 记录总数
        // 记录每个节点的祖先节点，
        // fa为并查集概念中，保存祖先节点的规范名称
        this.fa = new Array(n).fill(-1).map((_, idx) => idx);
    }

    find(i) {
        // 这是个递归方法

        // 如果元素的祖先就是自己，返回自身
        // 这里99%情况下，是递归自身的终点，不是向外部返回的终点
        // 下面这行return是返回到函数体内部的 fa[i] = find(fa[i]) 这句话上的
        if (this.fa[i] === i) return i;

        // 路径压缩，一旦查到了最终节点，就直接赋值给fa[i]，将中间的链条都切断，将fa[i]直连到祖先节点上
        // 这里接收递归终点的返回值
        this.fa[i] = this.find(this.fa[i]);
        return this.fa[i];
    }

    /**
     * 将i元素的祖先节点设置为j元素的祖先
     * @param {number} i
     * @param {number} j
     */
    union(i, j) {
        this.fa[this.find(i)] = this.find(j);
        this.outFa();
    }

    /**
     * 查询i关联的所有并集
     * @param {*} i
     * @returns
     */
    fetchJoint(i) {
        let nDad = this.find(i); // 找到祖先节点
        let ret = [];
        this.fa.forEach((_, idx) => {
            if (this.find(idx) === nDad) {
                ret.push(idx);
            }
        });

        return ret;
    }

    /**
     * 输出当前的并查集结果
     */
    outFa() {
        console.log(JSON.stringify(this.fa));
    }

    /** 统计当前并查集中，一共有几个不相干的子集，以及子集的个数是多少 */
    outAllNodes() {
        let hashMap = new HashMap();

        for (let i = 0; i < this.fa.length; i++) {
            const arr = this.fetchJoint(i);
            const key = arr.join('-');
            if (!hashMap.getByKey(key)) hashMap.add(arr.join('-'), arr.length);
        }

        return hashMap;
    }
}

console.log('[TEST]');
let max = 6;
console.log(`init ${max}`);
let disJoint = new DisJoint(max);
// disJoint.union(4, 3);
// disJoint.union(3, 2);
disJoint.union(2, 1);
disJoint.union(1, 0);
disJoint.union(4, 5);

console.log(`union complete:`);
disJoint.outFa();

const allNodes = new Array(6).fill(-1).map((_, idx) => idx);
allNodes.forEach((node) => {
    console.log(`fetch node:${node} joint`);
    console.log(disJoint.fetchJoint(node));
});

console.log(JSON.stringify(disJoint.outAllNodes().all()));

// console.log(`fetch complete:`);
// disJoint.outFa();
